// https://leetcode.cn/problems/merge-two-binary-trees/
// Created by ade on 2022/8/10.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 最笨的方法
    TreeNode *mergeTrees1(TreeNode *root1, TreeNode *root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        return dfs(root1, root2);
    }

    TreeNode *dfs(TreeNode *n1, TreeNode *n2) {
        if (!n1 && !n2) return nullptr;
        TreeNode *tmp = new TreeNode();
        if (n1 && n2) {
            tmp->val += n1->val;
            tmp->val += n2->val;
            tmp->left = dfs(n1->left, n2->left);
            tmp->right = dfs(n1->right, n2->right);
        } else if (!n1) {
            tmp->val += n2->val;
            tmp->right = dfs(nullptr, n2->right);
            tmp->left = dfs(nullptr, n2->left);
        } else {
            tmp->val += n1->val;
            tmp->left = dfs(n1->left, nullptr);
            tmp->right = dfs(n1->right, nullptr);
        }

        return tmp;
    }

    // 官方解法
    TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        TreeNode *head = new TreeNode(root1->val + root2->val);
        head->left = mergeTrees(root1->left, root2->left);
        head->right = mergeTrees(root1->right, root2->right);
        return head;
    }

    TreeNode *init() {
        TreeNode *h1 = new TreeNode(1);
        TreeNode *h2 = new TreeNode(2);
        TreeNode *h3 = new TreeNode(3);
        TreeNode *h4 = new TreeNode(4);
        h1->left = h2;
        h2->left = h4;
        h1->right = h3;
        return h1;
    }

    void show(TreeNode *node) {
        if (!node) return;
        cout << node->val << ",";
        show(node->left);
        show(node->right);
    }
};

int main() {
    Solution so;
    TreeNode *h1 = so.init();
    TreeNode *h2 = so.init();
    auto res = so.mergeTrees(h1, h2);
    so.show(res);
    return 0;
}